coding theory Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and data storage. Codes are stud ...

, a parity-check matrix of a

linear block code In coding theory, block codes are a large and important family of error-correcting codes that encode data in blocks. There is a vast number of examples for block codes, many of which have a wide range of practical applications. The abstract definit ...

''C'' is a matrix which describes the linear relations that the components of a

codeword In communication, a code word is an element of a standardized code or protocol. Each code word is assembled in accordance with the specific rules of the code and assigned a unique meaning. Code words are typically used for reasons of reliability, ...

must satisfy. It can be used to decide whether a particular vector is a codeword and is also used in decoding algorithms.

Definition

Formally, a parity check matrix ''H'' of a linear code ''C'' is a

generator matrix In coding theory, a generator matrix is a matrix whose rows form a basis for a linear code. The codewords are all of the linear combinations of the rows of this matrix, that is, the linear code is the row space of its generator matrix. Terminol ...

of the

dual code In coding theory, the dual code of a linear code :C\subset\mathbb_q^n is the linear code defined by :C^\perp = \ where :\langle x, c \rangle = \sum_^n x_i c_i is a scalar product. In linear algebra terms, the dual code is the annihilator ...

, ''C''^⊥. This means that a codeword c is in ''C ''

if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bicondi ...

the matrix-vector product (some authors would write this in an equivalent form, c''H''^⊤ = 0.) The rows of a parity check matrix are the coefficients of the parity check equations. That is, they show how linear combinations of certain digits (components) of each codeword equal zero. For example, the parity check matrix :

H =

\left \begin
  0&0&1&1\\
  1&1&0&0
\end
\right

, compactly represents the parity check equations, :

\begin c_3 + c_4 &= 0 \\ c_1 + c_2 &= 0 \end

, that must be satisfied for the vector

(c_1, c_2, c_3, c_4)

to be a codeword of ''C''. From the definition of the parity-check matrix it directly follows the minimum distance of the code is the minimum number ''d'' such that every ''d - 1'' columns of a parity-check matrix ''H'' are linearly independent while there exist ''d'' columns of ''H'' that are linearly dependent.

Creating a parity check matrix

The parity check matrix for a given code can be derived from its

(and vice versa). If the generator matrix for an 'n'',''k''code is in standard form :

G = \begin I_k ,  P \end

, then the parity check matrix is given by :

H = \begin -P^ ,  I_ \end

, because :

G H^ = P-P = 0

. Negation is performed in the finite field F_''q''. Note that if the characteristic of the underlying field is 2 (i.e., 1 + 1 = 0 in that field), as in

binary code A binary code represents text, computer processor instructions, or any other data using a two-symbol system. The two-symbol system used is often "0" and "1" from the binary number system. The binary code assigns a pattern of binary digits, also ...

s, then -''P'' = ''P'', so the negation is unnecessary. For example, if a binary code has the generator matrix :

G = 
\left \begin
1&0&1&0&1 \\
0&1&1&1&0 \\
\end
\right /math>,

then its parity check matrix is

: H =
\left \begin
1&1&1&0&0 \\
0&1&0&1&0 \\
1&0&0&0&1 \\
\end
\right /math>.

It can be verified that G is a k \times n matrix, while H is a (n-k) \times n matrix.

Syndromes

For any (row) vector x of the ambient vector space, s = ''H''x^⊤ is called the

syndrome A syndrome is a set of medical signs and symptoms which are correlated with each other and often associated with a particular disease or disorder. The word derives from the Greek σύνδρομον, meaning "concurrence". When a syndrome is paired ...

of x. The vector x is a codeword if and only if s = 0. The calculation of syndromes is the basis for the

syndrome decoding In coding theory, decoding is the process of translating received messages into codewords of a given code. There have been many common methods of mapping messages to codewords. These are often used to recover messages sent over a noisy channel, su ...

algorithm.

Notes

References

* * * * {{cite book , author=J.H. van Lint , title=Introduction to Coding Theory , edition=2nd , publisher=Springer-Verlag , series= GTM , volume=86 , date=1992 , isbn=3-540-54894-7 , page
34
, url=https://archive.org/details/introductiontoco0000lint/page/34 Coding theory

Definition

Creating a parity check matrix

Syndromes

See also

Notes

References